package com.example.demo1.suanfa;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author zx
 * @Date 2022/2/17 15:37
 * @Version 1.0
 */
public class DongTaiGuiHua {

    /**
     给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     子数组 是数组中的一个连续部分。
     示例 1：
     输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     输出：6
     解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     */
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    public static void main(String[] args) {
        Map<String,String> hashMap = new HashMap();
        hashMap.put("haahah","hahaha1");

        DongTaiGuiHua dongTaiGuiHua = new DongTaiGuiHua();
        int[] array = {4,-1,2,1};
        int i = dongTaiGuiHua.maxSubArray(array);
    }



}
